/* 快速排序 */
#include <stdio.h>
#include "public.h"

void fastSw(int arr[],int i, int j,int k){

    //存储开始和结尾
    int s = i;
    int e = j;

    //当左右指针未交汇时，进行循环
    while( i!= j && i < j){

        //右侧找到第一个小于目标值的值
        while(arr[j] > arr[k]){
            j--;
        }

        //如果右侧找到的值和目标不重合，则交换
        if(k != j){
            swap(arr,j,k); 
            k = j;
        }

        //左侧找到第一个大于目标的值
        while (arr[k] > arr[i]){
            i++;
        }
        
        //不重合则交换
        if(k != i){
            swap(arr,k,i);
            k = i;
        }
        
    }

    //判断起点和终点的距离，小于2则终止递归
    if( (e - s) > 2){

        //递归左半部分
        fastSw(arr,s,k-1,s);
        
        //递归右半部分
        fastSw(arr,k+1,e,k+1);
    }

}

int main(){

     //定义无序数组
    int arr[] = {5,6,9,1,3,2,7,8,4,0};
    int len = sizeof(arr)/4;

    int i = 0,j = len - 1,k = 0;

    fastSw(arr,i,j,k);

    each(arr,len);
}